package FlowGraph.Transformations;

import java.util.*;

import antlr.collections.AST;
import antlr.*;

import FlowGraph.*;
import FlowGraph.Nodes.*;
import FlowGraph.EdgeInfo.*;
import SymbolTable.*;
import JavaGrammar.*;
import util.Util;

//////////////////////////////////////////////////////////////////////////
//// Transformation
/**
    Contem metodos basicos para transformacoes

@author Ivan Jeukens
@version v 0.1 11/11/2002
*/
public class Transformation {

    public Transformation(FlowGraph fg) {
        _flowGraph = fg;
    }

    ///////////////////////////////////////////////////////////////////
    ////                         public methods                    ////

    public void transform(LinkedList arguments) {
    }

    ///////////////////////////////////////////////////////////////////
    ////                      protected methods                    ////

    // adiciona um no antes de um no tipo DoCondition. Esse metodo e um
    // caso especial do metodo addNodeBefore, pois o scopo do novo no
    // deve ser o mesmo do corpo do laco
    protected void _addNodeBeforeDoCondition(FlowGraphNode toadd, FlowGraphNode node,
            boolean transferLabel) {
        toadd.setUniqueNum(_flowGraph.getUniqueCount());
        _flowGraph.incrementUniqueCount();

        // Eu sei que o node e o do condition...
        FlowGraphNode input = node.getInputNode(0);

        toadd.setSymbolTable(input.getSymbolTable(), false);

        LinkedAST childast = (LinkedAST) input.getAbsTreeNode();
        LinkedAST newast = (LinkedAST) toadd.getAbsTreeNode();
        LinkedAST parentast = (LinkedAST) childast.getParent();

        // eu quero inserir depois, e nao antes ... 
        childast.setNextSibling(newast);
        newast.setParent(childast);

        // Atualiza as conexoes
        toadd.setScope(input.getScope());
        toadd.closeScope();
        input.setClosedScopes(input.getClosedScopes() - 1);

        input.replaceOutputConnection(node, toadd);
	_flowGraph.connect(toadd, node);
        _flowGraph.addNode(toadd);

        // transfere o label se ele existir
        if(transferLabel) {
            if(node.getLabel() != null) {
                toadd.setLabel(node.getLabel());
                node.setLabel(null);
                for(int i = 0;i < node.inputSize();i++) {
                    FlowGraphNode bl = node.getInputNode(i);
                    if(bl.getType() == FlowGraphNode.BREAK) {
                        AST target = ((BreakNode)bl).getTarget();
                        if(target != null) {
                            _flowGraph.replaceConnection(bl, node, toadd);
                        }
                    }
                }
            }
        }
    }

    // Cria o ast de uma declaracao de variavel local.
    protected LinkedAST _createLocalVarAST(String varName, String typeName) {
        CommonToken tok = new CommonToken(JavaTokenTypes.VARIABLE_DEF, 
            new String("VARIABLE_DEF"));
	LinkedAST vardef = new LinkedAST(tok);

        tok = new CommonToken(JavaTokenTypes.MODIFIERS,
            new String("MODIFIERS"));
	LinkedAST ast = new LinkedAST(tok);
	vardef.addChild(ast);
	ast.setParent(vardef);

	tok = new CommonToken(JavaTokenTypes.TYPE, new String("TYPE"));
	LinkedAST ast2 = new LinkedAST(tok);

	ast.setNextSibling(ast2);
	ast2.setParent(ast);

        if(typeName == null) {
	    tok = new CommonToken(JavaTokenTypes.IDENT, new String("nome_do_tipo"));
	}
	else {
	    tok = new CommonToken(JavaTokenTypes.IDENT, typeName);
	}
	LinkedAST ast3 = new LinkedAST(tok);
	ast2.addChild(ast3);
	ast3.setParent(ast2);

	tok = new CommonToken(JavaTokenTypes.IDENT, new String(varName));
	LinkedAST ast4 = new LinkedAST(tok);

	ast2.setNextSibling(ast4);
	ast4.setParent(ast2);

        return vardef;
    }

    /* Adiciona um no antes do for begin, puxando todo for um nivel abaixo
    no scopo */
    protected void addNodeBeforeForBegin(FlowGraphNode toadd, SymbolTable st,
            ForBeginNode fbeg, boolean transferLabel) {
        toadd.setUniqueNum(_flowGraph.getUniqueCount());
        _flowGraph.incrementUniqueCount();

        toadd.setScope(fbeg.getScope() + 1);

        toadd.setOpenedScopes(fbeg.getOpenedScopes());
        toadd.setClosedScopes(0);
        fbeg.setOpenedScopes(0);

        ForEndNode end = fbeg.getForEnd();

        LinkedAST init = (LinkedAST) toadd.getAbsTreeNode();
        LinkedAST forast = (LinkedAST) fbeg.getAbsTreeNode();

        CommonToken token = new CommonToken(JavaTokenTypes.SLIST, "{");
        LinkedAST slast = new LinkedAST(token);
        
        LinkedAST prev = (LinkedAST) forast.getParent();
        boolean sibling = false;
        if(prev.getNextSibling() == forast) {
            sibling = true;
        }
        LinkedAST afterfor = (LinkedAST) forast.getNextSibling();

        init.setNextSibling(forast);
        forast.setParent(init);

        init.setParent(slast);
        slast.addChild(init);

        forast.setNextSibling(null);

        slast.setParent(prev);
        if(prev != null) {
            if(sibling) {
                prev.setNextSibling(slast);
            }
            else {
                prev.setFirstChild(slast);
            }
        }

        slast.setNextSibling(afterfor);
        if(afterfor != null) {
            afterfor.setParent(slast);
        }

        // Atualiza a hierarquia das ST locais
        if(st.localSize() == 0) {
            SymbolTable nodeST = fbeg.getSymbolTable();
            toadd.setSymbolTable(nodeST, false);
        }
        else {
            toadd.setSymbolTable(st, true);
            SymbolTable nodeST = fbeg.getSymbolTable();
            if(fbeg.hasVarDef()) {
                SymbolTable parent = nodeST.getNextTable();
                st.link(parent);
                nodeST.link(st);
            }
            else {
                // estava true!
                fbeg.setSymbolTable(st, false);
                st.link(nodeST);
    
                if(!fbeg.isEmptyLoop()) {
                    SymbolTable.updateNodeTable(fbeg,
                        fbeg.getForEnd(), nodeST, st);
                }
                else {
                    fbeg.getForEnd().setSymbolTable(st, false);
                }
            }
        }

        // Atualiza as conexoes
        for(int counter = 0;counter < fbeg.inputSize();counter++) {
            FlowGraphEdge edge = fbeg.getInputEdge(counter);
            // Isso e necessario para nos de inicio de lacos
            if(!edge.isBack()) {
                _flowGraph.replaceConnection(edge.getFrom(), fbeg, toadd);
            }
        }
	_flowGraph.connect(toadd, fbeg);
        _flowGraph.addNode(toadd);

        //_updateSymbolTable(fbeg, toadd, st);

        toadd.openScope();
        end.closeScope();

        // transfere o label se ele existir
        if(fbeg.getLabel() != null) {
            toadd.setLabel(fbeg.getLabel());
            fbeg.setLabel(null);
            for(int i = 0;i < fbeg.inputSize();i++) {
                FlowGraphNode bl = fbeg.getInputNode(i);
                if(bl.getType() == FlowGraphNode.BREAK) {
                    AST target = ((BreakNode)bl).getTarget();
                    if(target != null) {
                        _flowGraph.replaceConnection(bl, fbeg, toadd);
                    }
                }
            }
        }

        // Incrementa o valor do scope no nos do loop
        HashMap marked = new HashMap();
        LinkedList process = new LinkedList();
        fbeg.setScope(fbeg.getScope() + 1);
        for(int i = 0;i < fbeg.outputSize();i++) {
            process.add(fbeg.getOutputNode(i));
        }
        marked.put(fbeg, null);
        end.setScope(end.getScope() + 1);
        marked.put(end, null);
        while(process.size() > 0) {
            FlowGraphNode node = (FlowGraphNode) process.removeFirst();
            if(marked.containsKey(node)) continue;

            node.setScope(node.getScope() + 1);
            marked.put(node, null);

            if(node.getType() == FlowGraphNode.RETURN ||
               node.getType() == FlowGraphNode.CONTINUE ||
               node.getType() == FlowGraphNode.BREAK ||
               node.getType() == FlowGraphNode.THROW) {
                continue;
            }

            for(int i = 0;i < node.outputSize();i++) {
                FlowGraphEdge edge = node.getOutputEdge(i);
                if(!edge.isBack()) {
                    process.add(edge.getTo());
                }
            }

            // Nao rodei o addExceptionEdges ainda ....
            if(node.getType() == FlowGraphNode.TRY_BEGIN) {
                TryBeginNode tbeg = (TryBeginNode) node;
                for(int i = 0;i < tbeg.catchSize();i++) {
                    process.add(tbeg.getCatch(i));
                }
                FinallyBeginNode finode = tbeg.getFinally();
                if(finode != null) process.add(finode);
            }
            else
            if(node.getType() == FlowGraphNode.SWITCH_BEGIN) {
                SwitchBeginNode sbeg = (SwitchBeginNode) node;
                process.add(sbeg.getSwitchEnd());
            }
        }
    }

    // Adiciona um conjunto de expressoes no final do loop for.
    protected void _addBBEndLoop(ForBeginNode node, AST toadd) {
        int count = 0;
        FlowGraphNode inNode = null;
        BasicBlockNode toaddNode = null;
        // Se tiver mais de uma expressao na lista, tem que quebrar
        LinkedList astList = _breakEList(toadd);

        for(int i = 0;i < node.inputSize();i++) {
            FlowGraphEdge in = node.getInputEdge(i);
            inNode = in.getFrom();
            if(in.isBack()) {
                if(inNode.getType() == FlowGraphNode.CONTINUE) {
                    BasicBlockNode bb = _newBasicBlock(astList);
                    // E o var def??
                    FlowGraphNode in2 = inNode.getInputNode(0);
                    SymbolTable st = in2.getSymbolTable();

                    // Eu nao sei se a ST tem que ser nova.

                    _addNodeBefore(bb, st, inNode, false);
                    node.addIteExtractedNode(bb);
                }
                else {
                    toaddNode = _newBasicBlock(astList);
                    node.addIteExtractedNode(toaddNode);

                    _flowGraph.disconnect(inNode, node);
                    FlowGraphEdge edge = _flowGraph.connect(inNode, toaddNode);

                    if(inNode != node) {
                        toaddNode.setScope(inNode.getScope());
                        // menos o scope do loop
                        inNode.setClosedScopes(inNode.getClosedScopes() - 1);
                        // mais o scope do loop
                    }
                    // um loop com corpo vazio
                    else {
                       toaddNode.setScope(inNode.getScope() + 1);
                       toaddNode.openScope();
                    }
                    toaddNode.closeScope();
                    count++;
                }
            }
        }
        if(count > 1) {
            System.out.println("addNodeEndLoop error!!!! -> count  > 1");
        }
        FlowGraphEdge edge = _flowGraph.connect(toaddNode, node);
        BackEdge be = new BackEdge();
        edge.setEdgeInfo(be);

        // e se tiver definicoes no innode....
        toaddNode.setSymbolTable(inNode.getSymbolTable(), false);

        LinkedAST ast2 = (LinkedAST) toaddNode.getAbsTreeNode();
        if(inNode != node) {
            LinkedAST ast = (LinkedAST) inNode.getAbsTreeNode();
            ast.setNextSibling(ast2);
            ast2.setParent(ast);
        }
        else {
            LinkedAST ast = (LinkedAST) node.getAbsTreeNode();
            ast = (LinkedAST) ast.getFirstChild();
            while(ast.getNextSibling() != null) {
                ast = (LinkedAST) ast.getNextSibling();
            }
            ast.setFirstChild(ast2);
            ast2.setParent(ast);
        }
        ast2.setNextSibling(null);

        _flowGraph.addNode(toaddNode);
    }

    /** Adiciona o mc extraido ao final do corpo do loop. Funciona para while
        O parametro node e a cabeca do loop.
    **/
    protected void _addNodeEndLoop(FlowGraphNode toadd, FlowGraphNode node, 
            AST toaddAST, AST ast5, HashMap skipMCTable) {
        toadd.setUniqueNum(_flowGraph.getUniqueCount());
        _flowGraph.incrementUniqueCount();

        int count = 0;
        FlowGraphNode inNode = null;

        // Serve para for e while
        LoopHeadNode loophead = (LoopHeadNode) node;
        for(int i = 0;i < node.inputSize();i++) {
            FlowGraphEdge in = node.getInputEdge(i);
            inNode = in.getFrom();
            if(in.isBack()) {
                if(inNode.getType() == FlowGraphNode.CONTINUE) {
                    AST newmc = Util.dupTree(toaddAST);
                    MethodCallNode mc = new MethodCallNode(newmc);

                    mc.setVarDef(false);
                    if(ast5 != null) {
                        AST ast = newmc;
                        ast = ast.getFirstChild();
                        ast = ast.getFirstChild();
                        ast = ast.getNextSibling();
                        skipMCTable.put(mc, ast);
                    }

                    FlowGraphNode in2 = inNode.getInputNode(0);
                    SymbolTable st = in2.getSymbolTable();

                    // Eu nao sei se a ST tem que ser nova.

                    _addNodeBefore(mc, st, inNode, false);
                    loophead.addIteExtractedNode(mc);
                    continue;
                }
                _flowGraph.disconnect(inNode, node);
                FlowGraphEdge edge = _flowGraph.connect(inNode, toadd);

                if(inNode != node) {
                    toadd.setScope(inNode.getScope());
                    // menos o scope do loop
                    inNode.setClosedScopes(inNode.getClosedScopes() - 1);
                    // mais o scope do loop
                }
                // um loop com corpo vazio
                else {
                   toadd.setScope(inNode.getScope() + 1);
                   toadd.openScope();
                }
                toadd.closeScope();
                count++;
            }
        }

        if(count > 1) {
            System.out.println("addNodeEndLoop error!!!! -> count  > 1");
        }
        
        FlowGraphEdge edge = _flowGraph.connect(toadd, node);
        BackEdge be = new BackEdge();
        edge.setEdgeInfo(be);

        toadd.setSymbolTable(inNode.getSymbolTable(), false);

        LinkedAST ast2 = (LinkedAST) toadd.getAbsTreeNode();
        if(inNode != node) {
            LinkedAST ast = (LinkedAST) inNode.getAbsTreeNode();
            ast.setNextSibling(ast2);
            ast2.setParent(ast);
        }
        else {
            LinkedAST ast = (LinkedAST) node.getAbsTreeNode();
            ast = (LinkedAST) ast.getFirstChild();
            while(ast.getNextSibling() != null) {
                ast = (LinkedAST) ast.getNextSibling();
            }
            ast.setFirstChild(ast2);
            ast2.setParent(ast);
        }
        ast2.setNextSibling(null);

        _flowGraph.addNode(toadd);
        loophead.addIteExtractedNode(toadd);
    }
    
    /* Adiciona um no ao grafo, antecedendo o no especificado. Todas
    as conexoes sao atualizadas. A ST do novo no tambem deve ser
    especificada. Considero que e no mesmo scopo */
    protected void _addNodeBefore(FlowGraphNode toadd, SymbolTable st,
            FlowGraphNode node, boolean transferLabel) {
        _updateState(toadd, node);
        _updateAST(toadd, node);
        _updateConnections(toadd, node, transferLabel);

        // o update necessita das novas conexoes
        _updateSymbolTable(node, toadd, st);
    }

    protected LinkedList _breakEList(AST elist) {
        LinkedList ret = new LinkedList();
        AST ast = elist;
        while(ast != null) {
            AST nexts = ast.getNextSibling();
            ast.setNextSibling(null);
            ret.add(ast);
            ast = nexts;
        }
        return ret;
    }

    protected BasicBlockNode _newBasicBlock(LinkedList expressions) {
        BasicBlockNode ret = new BasicBlockNode();
        for(int i = 0;i < expressions.size();i++) {
            AST dup = Util.dupTree((AST) expressions.get(i));
            ret.addStatement(dup);
        }
        return ret;
    }
    
    ///////////////////////////////////////////////////////////////////
    ////                        private methods                    ////   

    private void _updateState(FlowGraphNode toadd, FlowGraphNode node) {
        toadd.setUniqueNum(_flowGraph.getUniqueCount());
        _flowGraph.incrementUniqueCount();
        toadd.setScope(node.getScope());

        toadd.setOpenedScopes(node.getOpenedScopes());
        toadd.setClosedScopes(0);
        node.setOpenedScopes(0);

        _flowGraph.addNode(toadd);
    }
    
    private void _updateAST(FlowGraphNode toadd, FlowGraphNode node) {
        // Inclui o ast do novo no na arvore
        LinkedAST childast = (LinkedAST) node.getAbsTreeNode();
        LinkedAST newast = (LinkedAST) toadd.getAbsTreeNode();
        LinkedAST parentast = (LinkedAST) childast.getParent();
        newast.setNextSibling(childast);
        newast.setParent(parentast);

        if(parentast.getFirstChild() == childast) {
            parentast.setFirstChild(newast);
        }
        else {
            parentast.setNextSibling(newast);
        }
        childast.setParent(newast);
    }
    
    private void _updateConnections(FlowGraphNode toadd, FlowGraphNode node,
             boolean transferLabel) {
        // Atualiza as conexoes
        LinkedList process = new LinkedList();
        Iterator ite = node.inputEdgesIterator();
        while(ite.hasNext()) {
            FlowGraphEdge edge = (FlowGraphEdge) ite.next();
            if(!edge.isBack()) {
                process.add(edge);
            }
        }
        for(int i = 0;i < process.size();i++) {
            FlowGraphEdge edge = (FlowGraphEdge) process.get(i);
            _flowGraph.replaceConnection(edge.getFrom(), node, toadd);
        }
	_flowGraph.connect(toadd, node);

        // transfere o label se ele existir
        if(transferLabel) {
            if(node.getLabel() != null) {
                toadd.setLabel(node.getLabel());
                node.setLabel(null);
                for(int i = 0;i < node.inputSize();i++) {
                    FlowGraphNode bl = node.getInputNode(i);
                    if(bl.getType() == FlowGraphNode.BREAK) {
                        AST target = ((BreakNode)bl).getTarget();
                        if(target != null) {
                            _flowGraph.replaceConnection(bl, node, toadd);
                        }
                    }
                }
            }
        }
    }

    /* A performance deste metodo nao e satisfatoria */
    private void _updateSymbolTable(FlowGraphNode node, FlowGraphNode toadd,
            SymbolTable st) {
        SymbolTable nodeST = node.getSymbolTable();
        SymbolTable parentST;

        if(node.hasVarDef()) {
            parentST = nodeST.getNextTable();
        }
        else {
            parentST = nodeST;
        }
        FlowGraphNode parentNode = parentST.getOwner();

        SymbolTable newst = (SymbolTable) parentST.clone();
        parentNode.setSymbolTable(newst, true);

        parentST.clear();
        Iterator ite = st.iterator();
        while(ite.hasNext()) {
            STEntry entry = (STEntry) ite.next();
            parentST.putElement(entry.getName(), entry);
        }
        parentST.link(newst);
        toadd.setSymbolTable(parentST, true);
        SymbolTable outside = newst.getNextTable();

        LinkedList processed = new LinkedList();
        HashMap done = new HashMap();
        processed.add(parentNode);
        LinkedList stopnodes = new LinkedList();
        _searchST(processed, stopnodes, done, toadd, parentST, newst, outside, false);
    }
    
    private boolean _searchST(LinkedList processed, LinkedList stopnodes, HashMap done,
            FlowGraphNode toadd, SymbolTable parentST, SymbolTable newst,
            SymbolTable outside, boolean processingSwitch) {
        while(processed.size() > 0) {
            FlowGraphNode fgnode = (FlowGraphNode) processed.removeFirst();
            if(done.containsKey(fgnode)) continue;

            if(stopnodes.contains(fgnode)) return false;
            if(fgnode == toadd) {
                if(!processingSwitch) {
                    continue;
                }
                else {
                    return true;
                }
            }
            done.put(fgnode, null);
            SymbolTable st2 = fgnode.getSymbolTable();
            if(st2 == parentST) {
                fgnode.setSymbolTable(newst, false);
            }
            else
            if(st2.getNextTable() == parentST) {
                st2.link(newst);
            }
            // como a tabela outside esta fora do scope, nenhum no a partir
            // deste pode estar liguado a parentST
            if(st2 == outside) continue;

            if(fgnode.getType() == FlowGraphNode.RETURN ||
                fgnode.getType() == FlowGraphNode.THROW) continue;

            if(fgnode.getType() == FlowGraphNode.SWITCH_BEGIN) {
                SwitchBeginNode beg = (SwitchBeginNode) fgnode;
                for(int i = 0;i < beg.outputSize();i++) {
                    FlowGraphNode fn = beg.getOutputNode(i);
                    if(fn.getOpenedScopes() > 0) continue;

                    stopnodes.add(beg.getCaseEndNode(i));
                    LinkedList newprocessed = new LinkedList();
                    newprocessed.add(fn);
                    boolean v = _searchST(newprocessed, stopnodes, done, toadd, parentST, newst,
                        outside, true);
                    stopnodes.removeLast();
                    // Eu achei o toadd dentro de um dos caminhos do switch. Deixe
                    // o resto intacto
                    if(v) break;
                }
                for(int i = 0;i < beg.outputSize();i++) {
                    FlowGraphNode fn = beg.getOutputNode(i);
                    if(fn.getOpenedScopes() == 0) continue;
                    processed.add(fn);
                }
                processed.add(beg.getSwitchEnd());
            }
            else {
                for(int i = 0;i < fgnode.outputSize();i++) {
                    FlowGraphEdge edge = fgnode.getOutputEdge(i);
                    FlowGraphNode to = edge.getTo();
                    if(!edge.isBack() && !done.containsKey(to)) {
                        processed.add(edge.getTo());
                    }
                }
            }

            if(fgnode.getType() == FlowGraphNode.SWITCH_END) {
                SwitchEndNode end = (SwitchEndNode) fgnode;
                SwitchBeginNode swbeg = end.getSwitchBegin();
                // Cheguei no switch end, sem passar pelo begin. Entao,
                // e porque o no foi atualizado dentre de um case.                
                if(!done.containsKey(swbeg)) {
                    processed.add(swbeg);
                }
            }
        }

        return false;
    }

    ///////////////////////////////////////////////////////////////////
    ////                      protected variables                  ////

    protected FlowGraph _flowGraph;

    ///////////////////////////////////////////////////////////////////
    ////                        private variables                  ////
    
}
